// https://leetcode.cn/problems/jump-game/description/

// 算法思路总结：
// 1. 贪心策略处理跳跃游戏问题
// 2. 维护当前可到达的最远距离，遍历数组更新最远距离
// 3. 如果当前位置超出当前最远距离则返回失败
// 4. 如果最远距离已覆盖终点则提前返回成功
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool canJump(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return true;

        int l = 0, r = nums[0];
        while (l + r < m - 1)
        {
            int tmpIndex = 0, tmpSum = 0;
            for (int i = 1 ; i <= r ; i++)
            {
                if (i + nums[l + i] > tmpSum)
                {
                    tmpIndex = l + i;
                    tmpSum = i + nums[l + i];
                }   
            }
            l = tmpIndex;
            r = nums[l];
            if (r == 0) return false;
        }

        return true;
    }
};

int main()
{
    vector<int> v1 = {2,3,1,1,4}, v2 = {3,2,1,0,4};
    Solution sol;

    cout << sol.canJump(v1) << endl;
    cout << sol.canJump(v2) << endl;

    return 0;
}
